W1. Introduction to Theoretical Computer Science, Golden Ratio and Fibonacci, Course Structure, Models of Computation

1. Summary

1.1 The Golden Ratio and Fibonacci Sequence

The golden ratio (denoted by the Greek letter \(\phi\), pronounced “phi”) is a special irrational number approximately equal to 1.618. Like \(\pi\) (pi), the golden ratio is an irrational number, meaning its decimal digits continue forever without repeating any pattern. This number appears throughout nature, art, architecture, and mathematics, often associated with aesthetically pleasing proportions.

1.1.1 The Fibonacci Sequence

The Fibonacci sequence is a sequence of numbers where each number is the sum of the two preceding ones. The sequence begins: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

Mathematically, we can define it as:

• \(F_1 = 1\)
• \(F_2 = 1\)
  
• \(F_n = F_{n-1} + F_{n-2}\) for \(n > 2\)

The Fibonacci sequence has a remarkable connection to the golden ratio. If we divide each Fibonacci number by the previous one, creating a sequence of ratios, this sequence converges to \(\phi\).

What does “converges” mean? In mathematics, we say a sequence converges to a value \(L\) if the terms of the sequence get arbitrarily close to \(L\) as we go further and further. No matter how small a distance you choose (say, 0.001 or 0.0000001), eventually all terms beyond a certain point will be within that distance of \(L\). The terms never quite reach \(L\), but they get infinitely close.

1.1.2 Convergence to the Golden Ratio

Let’s examine the ratios \(r(n) = \frac{F_{n+1}}{F_n}\):

• \(r(1) = \frac{1}{1} = 1\)
• \(r(2) = \frac{2}{1} = 2\)
• \(r(3) = \frac{3}{2} = 1.5\)
• \(r(4) = \frac{5}{3} = 1.67\)
• \(r(5) = \frac{8}{5} = 1.6\)
• \(r(6) = \frac{13}{8} = 1.625\)
• \(r(7) = \frac{21}{13} = 1.6125\)

As we continue, these ratios approach \(\phi = 1.61803398...\)

An interesting pattern emerges: the odd-indexed terms (1st, 3rd, 5th, …) are all less than the golden ratio, while the even-indexed terms (2nd, 4th, 6th, …) are all greater than the golden ratio. The sequence oscillates around \(\phi\), getting progressively closer with each term.

The exact value of the golden ratio can be expressed as: \[\phi = \frac{1 + \sqrt{5}}{2}\]

This formula arises from solving the equation \(x^2 = x + 1\), which captures the self-similar property of the golden ratio: \(\phi^2 = \phi + 1\). This means that if you square \(\phi\), you get \(\phi\) plus 1, reflecting the recursive nature of the Fibonacci sequence.

1.1.3 Golden Rectangle and Golden Spiral

The golden rectangle is a rectangle whose side lengths are in the golden ratio (length to width = \(\phi\)). When you remove a square from a golden rectangle, the remaining rectangle is also a golden rectangle. This property allows us to create a nested pattern of squares and rectangles.

Golden rectangle decomposition with Fibonacci-sized squares

If we draw a quarter-circle arc through opposite corners of each square in the golden rectangle arrangement (with squares of sides 1, 1, 2, 3, 5, 8, …), we create the golden spiral, also known as the Fibonacci spiral. This spiral appears frequently in nature.

1.2 The Golden Ratio in Nature and Human Design

1.2.1 The Golden Ratio in Human Anatomy

The golden ratio appears in human body proportions. For example, the bones in our fingers (called phalanges) have lengths that approximate the Fibonacci sequence. The ratio of successive phalanx lengths approaches the golden ratio. This arrangement allows our hand to form a perfect curl when we clench our fist, with the fingertips following a spiral path.

Facial features also exhibit golden ratio proportions. The positions of the ear, chin, nose, and other facial features often align with a golden spiral overlay, contributing to what many perceive as facial beauty.

1.2.2 The Golden Ratio in Architecture

Architects and designers have used the golden ratio for centuries to create aesthetically pleasing structures. One example is the Bramante Staircase at the Vatican Museums, designed by Giuseppe Momo in 1932. This double-helix staircase exhibits spiral geometry related to the golden ratio.

Medieval European cathedrals were often based on sacred geometry—using mathematical proportions to represent spiritual concepts and “show the world through mathematics” to gain a better understanding of the divine. Renaissance architect Leon Battista Alberti wrote De re aedificatoria (On the Art of Building, 1443-1452), which described the ideal church in terms of spiritual geometry using circles, squares, and proportions.

Leonardo da Vinci’s famous Vitruvian Man (circa 1490) illustrates the proportions of the human body according to ancient architect Vitruvius, demonstrating sacred geometry principles where the human form fits perfectly within both a circle and a square.

1.2.3 The Golden Ratio in Music

Composers and instrument makers have used the Fibonacci sequence and golden ratio in music for hundreds of years. Mozart’s Piano Sonata No. 1 provides a fascinating example. The first movement has 100 bars total:

• Exposition: 38 bars (call this \(A\))
• Development & Recapitulation: 62 bars (call this \(B\))
• Ratio: \(\frac{B}{A} = \frac{62}{38} = 1.6\)

This ratio is remarkably close to the golden ratio. Whether Mozart did this consciously or intuitively remains an open question.

The legendary violin maker Stradivari designed his instruments with proportions based on the golden ratio. The ratios of the body length, upper bout, and lower bout measurements of Stradivarius instruments closely approximate \(\phi\), potentially contributing to their renowned sound quality.

1.2.4 The Golden Ratio in Modern Design

Many modern corporate logos are designed using golden ratio geometry. Examples include:

• Twitter/X: The bird logo is constructed from overlapping circles whose radios follow golden ratio proportions
• National Geographic: The yellow rectangle has dimensions in the golden ratio (1:1.618)
• Chevron: The ribbons are designed with 1 and 1.618 proportional measurements
• BP: The concentric circles in the sunburst follow the golden ratio
• Pepsi: The circular logo uses circles with diameters in golden ratio proportions
• Toyota: The three ovals are enclosed in a rectangle with 1.618 proportions

The golden ratio is widely used because it creates designs that are aesthetically pleasing to the human eye.

1.3 Mathematics and Its Practical Applications

1.3.1 The Unexpected Utility of Pure Mathematics

John von Neumann, one of the greatest mathematicians of the 20th century, made an important observation about the relationship between pure mathematics and practical applications. In his 1954 address “The Role of Mathematics in the Sciences and in Society,” he stated:

“A large part of mathematics which becomes useful developed with absolutely no desire to be useful, and in a situation where nobody could possibly know in what area it would become useful; and there were no general indications that it ever would be so.”

Von Neumann further noted:

“By and large it is uniformly true in mathematics that there is a time lapse between a mathematical discovery and the moment when it is useful; and that this lapse of time can be anything from 30 to 100 years, in some cases even more; and that the whole system seems to function without any direction, without any reference to usefulness, and without any desire to do things which are useful.”

This principle is crucial in theoretical computer science: many mathematical concepts developed centuries ago without any practical purpose have become foundational to modern computing.

1.3.2 Historical Example: Number Theory and Cryptography

A perfect illustration of von Neumann’s principle is the relationship between number theory and modern cryptography. Number theory is a branch of pure mathematics studying properties of integers, developed over centuries by mathematicians with no thought of practical applications.

However, modern cryptographic systems depend entirely on number theory:

• RSA encryption (widely used for secure internet communications) is based on the difficulty of factoring large numbers—a purely number-theoretic problem
• Bitcoin and other cryptocurrencies rely on cryptographic schemes built on number-theoretic problems
• In 1994, cryptography faced a foundational crisis when Peter Shor showed that quantum computers could efficiently solve the number-theoretic problems underlying RSA and similar systems

This raises an important question: Will every cryptographic scheme based on number-theoretic problems become insecure once quantum computers become practical? This question drives ongoing research in post-quantum cryptography.

1.4 What is Theoretical Computer Science?

Theoretical Computer Science (TCS) is the mathematical study of computation itself. While practical computer science focuses on building systems and writing programs, theoretical computer science asks fundamental questions:

• What can be computed?
• What cannot be computed?
• How efficiently can problems be solved?
• What are the fundamental limits of computation?

1.4.1 Computability vs. Complexity

Two central concepts in theoretical computer science are:

• Computability: The study of what can be computed, regardless of time or resources. A problem is computable if there exists an algorithm that can solve it (even if that algorithm might take billions of years).
• Complexity: The study of how efficiently problems can be computed. Even if a problem is computable, it might require so much time or memory that it’s impractical to solve. We measure efficiency using Big O notation, like \(\mathcal{O}(n)\) for linear time or \(\mathcal{O}(n \log n)\) for sorting algorithms.

What is Big O Notation? Big O notation describes how the running time or space requirements of an algorithm grow as the input size increases. For example:

• \(\mathcal{O}(1)\): Constant time—takes the same time regardless of input size
• \(\mathcal{O}(n)\): Linear time—time doubles when input doubles
• \(\mathcal{O}(n^2)\): Quadratic time—time quadruples when input doubles
• \(\mathcal{O}(n \log n)\): Linearithmic time—typical for efficient sorting algorithms

The famous P vs NP problem asks whether every problem whose solution can be quickly verified can also be quickly solved—one of the most important unsolved questions in computer science and mathematics.

1.4.2 Why Study Theoretical Computer Science?

Understanding theoretical computer science is essential for several reasons:

1. Understanding compilers: A compiler translates high-level programming languages into machine code. This process relies heavily on theoretical concepts like formal grammars, automata theory, and language recognition. Without understanding these foundations, you cannot truly understand how programming languages work.
2. Avoiding computational limits: Just as physics tells us we cannot accelerate indefinitely due to friction and energy constraints, computability theory tells us there are fundamental limits to what computers can do. Understanding these limits prevents wasting time on impossible problems.
3. Better problem-solving: A software developer ignorant of how compilers work “is not better than a good pilot when it comes to fixing the engine.” Understanding theory allows you to provide more than average solutions and truly optimize systems.
4. Historical perspective: Understanding the great minds and results behind modern computing gives context to current technology and informs future innovation.

1.5 Course Information and Structure

1.5.1 Course Prerequisites

While this course aims to be self-contained, it’s recommended that students have basic knowledge of:

• Logic: Understanding logical statements, proofs, and reasoning
• Discrete Mathematics: Sets, relations, functions, and proof techniques
• Algorithms and Data Structures: Basic algorithmic thinking (helpful but not required)
• Calculus I: Some mathematical maturity (less critical than the others)

The course will review necessary mathematical foundations as needed.

1.5.2 Course Topics

The course covers the following major topics:

1. Language properties: Operations on languages, the Kleene operator (Kleene star), language cardinality
2. Finite State Automata (FSA): The simplest computational model
3. Pushdown Automata (PDA): Automata with stack memory
4. Regular expressions and regular languages: Pattern matching and language description
5. Relationships between automata and languages: Pumping lemma, closure properties
6. Formal grammars: Chomsky hierarchy of grammars and productions
7. Turing Machines (TM): The most powerful known computational model
8. Computability theory: Halting problem, Turing computability, Rice’s theorem
9. Lambda calculus (\(\lambda\)-calculus): An alternative model of computation (time permitting)

1.5.3 Course Structure and Assessment

Weekly Schedule:

• Lectures: Thursday 09:00-10:30 in Room 108
• Tutorials: Thursday 10:40-12:10 (all groups, Room 108)
• Lab sessions: Thursday afternoon slots (12:40-19:10, various rooms by group)

Labs begin on January 29, 2026, and generally cover topics from the previous week’s lecture.

Workload: The course is 6 credits, corresponding to approximately 10 hours per week:

• 6 hours of lectures, tutorials, and labs
• 4-6 hours of self-study

Assessment (Total: 105 points):

• Mid-term Exam: 30 points
• Final Exam: 30 points
• Assignments: 40 points (two assignments)
• Participation: 5 points

Assignments will be released around week 6 (late February/early March 2026) and week 13 (second half of April 2026).

1.5.4 Course Resources

Recommended Textbooks:

1. J.E. Hopcroft and J.D. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison Wesley (1979).
2. M. Davis, R. Sigal, and E.J. Weyuker. Computability, complexity, and languages: fundamentals of theoretical computer science. 2nd ed., Academic Press (1994).
3. J. Hromkovic. Algorithmic Adventures: From Knowledge to Magic. Springer (2009).

All materials, grades, and announcements are available on Moodle: [S26] Theoretical Computer Science.

1.6 Historical Context and Timeline

Understanding theoretical computer science requires appreciating its historical development:

• ~600 BC: The Epimenides paradox (also known as the “liar paradox”) raised questions about self-reference in logic. Epimenides, a Cretan, stated “All Cretans are liars,” creating a logical contradiction if the statement is true.
• 1936: Between World War I and World War II, Alan Turing proved that a general procedure to determine whether an arbitrary algorithm terminates (the halting problem) does not and cannot exist. This was a foundational result in computability theory.
• 1956: Noam Chomsky described a hierarchy of grammars (the Chomsky hierarchy), classifying formal languages by the types of grammars that can generate them. This became fundamental to compiler design and programming language theory.
• 1467: Even earlier, Leon Battista Alberti invented the Alberti cipher, one of the first polyalphabetic substitution ciphers, showing early connections between mathematics and information encoding.

The act of compilation—translating high-level code to machine code—appears deceptively simple today, but it rests on centuries of mathematical and logical development by great minds.

1.7 Foundational Concepts: Languages and Strings

Before we can understand models of computation, we need to understand what these models compute. In theoretical computer science, computation is viewed as processing strings to determine if they belong to specific languages.

1.7.1 Alphabet, Strings, and Languages

An alphabet is a finite, non-empty set of symbols. We typically denote alphabets with the Greek letter \(\Sigma\) (uppercase sigma). For example:

• \(\Sigma_1 = \{0, 1\}\) (binary alphabet)
• \(\Sigma_2 = \{a, b, c, \ldots, z\}\) (lowercase English letters)
• \(\Sigma_3 = \{(, ), +, -, \times, \div\}\) (mathematical symbols)

A string (also called a word) is a finite sequence of symbols from an alphabet. For example, if \(\Sigma = \{0, 1\}\), then \(0101\), \(1100\), and \(0\) are all strings over \(\Sigma\). The empty string (containing no symbols) is denoted by \(\epsilon\) (epsilon) or \(\lambda\) (lambda).

The length of a string \(w\), denoted \(|w|\), is the number of symbols it contains. For example:

• \(|0101| = 4\)
• \(|hello| = 5\)
• \(|\epsilon| = 0\)

A language \(L\) is a set of strings over an alphabet \(\Sigma\). This is a mathematical definition, not related to programming languages like Python or Java (though there is a connection we’ll see later). For example:

• \(L_1 = \{0, 01, 011, 0111, \ldots\}\) = strings starting with \(0\) followed by any number of \(1\)’s
• \(L_2 = \{\epsilon, 00, 0000, 000000, \ldots\}\) = strings with an even number of \(0\)’s
• \(L_3 = \{w : w \text{ contains equal numbers of } 0\text{'s and } 1\text{'s}\}\)

Languages can be:

• Finite: \(L = \{hello, world\}\) contains exactly two strings
• Infinite: \(L = \{0^n : n \geq 0\} = \{\epsilon, 0, 00, 000, \ldots\}\) contains infinitely many strings

1.7.2 What Does “Recognize” or “Accept” Mean?

When we say an automaton recognizes or accepts a language \(L\), we mean:

1. Given any string \(w\) as input, the automaton processes it symbol-by-symbol
2. After reading all symbols, the automaton either accepts (says “yes, this string is in \(L\)”) or rejects (says “no, this string is not in \(L\)”)
3. The automaton accepts exactly those strings that belong to \(L\), and rejects all others

Example: Consider a language \(L = \{w : w \text{ has an even number of } 1\text{'s}\}\) over alphabet \(\{0, 1\}\).

An automaton recognizing this language would:

• Accept: \(\epsilon\) (zero \(1\)’s, which is even), \(11\), \(0110\), \(1001\)
• Reject: \(1\), \(001\), \(111\), \(0101\)

The automaton doesn’t “compute” a number or return a value—it makes a binary decision: accept or reject.

1.8 Models of Computation

A model of computation is a mathematical abstraction that describes how computation happens. Different models capture different computational capabilities.

1.8.1 The Basic Computer Model

At the highest level, computation involves:

• CPU (Central Processing Unit): Performs operations
• Memory: Stores data and instructions
• Input/Output: Receives data and produces results

Basic computer model: computation as interaction between input, CPU, memory, and output

The CPU executes instructions stored in program memory, uses temporary memory to hold intermediate results, reads input, and produces output.

Example: Computing \(f(x) = x^3\) for \(x = 2\)

1. Program memory contains instructions:
   • Compute \(x \times x\) (gives \(x^2\))
   • Compute \(x^2 \times x\) (gives \(x^3\))
2. Input: \(x = 2\)
3. Processing:
   • Temporary memory: \(z = 2 \times 2 = 4\)
   • Temporary memory: \(f(x) = z \times 2 = 8\)
4. Output: \(f(x) = 8\)

1.8.2 The Automaton Abstraction

An automaton is a mathematical model that abstracts the CPU as a collection of states (representing the CPU’s configuration) and transitions (representing how the CPU moves from one state to another). The automaton still interacts with memory, input, and output.

Automaton abstraction: finite control interacts with input, memory, and output through labeled transitions

What is a State? A state represents a particular configuration or “mode” the automaton is in. Think of it like this:

• A traffic light has three states: RED, YELLOW, GREEN
• A vending machine might have states: IDLE, COINS_INSERTED, DISPENSING
• Your computer might be in states: RUNNING, SLEEP_MODE, POWERED_OFF

What is a Transition? A transition is a rule that tells the automaton how to move from one state to another based on input. For example:

• Traffic light: “If in GREEN state and 30 seconds pass → transition to YELLOW”
• Vending machine: “If in IDLE state and coin inserted → transition to COINS_INSERTED”
• Automaton processing strings: “If in state \(q_1\) and reading symbol \(0\) → transition to state \(q_2\)”

Different types of automata have different memory capabilities, giving them different computational power.

1.8.3 Three Types of Automata

1. Finite State Automata (FSA)

• Memory: NO external temporary memory; only the current state stores information
• Power: “Small” computing power
• Examples: Elevators, vending machines, simple pattern matching
• Languages recognized: Regular languages

Finite state automata have a fixed number of states and can only remember a limited amount of information (encoded in which state they’re in).

FSA for strings with an even number of 1s

Concrete Example of an FSA:

Let’s design an FSA to recognize the language \(L = \{w : w \text{ contains an even number of } 1\text{'s}\}\) over alphabet \(\{0, 1\}\).

The automaton needs only two states:

• State \(q_0\) (EVEN): “I’ve seen an even number of \(1\)’s so far”
• State \(q_1\) (ODD): “I’ve seen an odd number of \(1\)’s so far”

Transitions:

• From \(q_0\): If you read \(0\) → stay in \(q_0\) (zeros don’t affect count)
• From \(q_0\): If you read \(1\) → go to \(q_1\) (even → odd)
• From \(q_1\): If you read \(0\) → stay in \(q_1\) (zeros don’t affect count)
• From \(q_1\): If you read \(1\) → go to \(q_0\) (odd → even)

Start state: \(q_0\) (initially, we’ve seen zero \(1\)’s, which is even) Accept state: \(q_0\) (accept if we end in the EVEN state)

Trace example - Input string “0110”:

1. Start in \(q_0\) (EVEN)
2. Read \(0\) → stay in \(q_0\) (seen 0 ones)
3. Read \(1\) → transition to \(q_1\) (seen 1 one - odd)
4. Read \(1\) → transition to \(q_0\) (seen 2 ones - even)
5. Read \(0\) → stay in \(q_0\) (seen 2 ones - still even)
6. End in \(q_0\) (accept state) → ACCEPT ✓

The FSA correctly accepts “\(0110\)” because it contains two \(1\)’s (an even number).

2. Pushdown Automata (PDA)

• Memory: A stack (last-in, first-out data structure)
• Operations: Push (add to stack) and Pop (remove from stack, destructively)
• Power: “Medium” computing power
• Examples: Compilers for programming languages, parsing nested structures
• Languages recognized: Context-free languages

Pushdown automata can recognize more complex patterns than FSAs, such as balanced parentheses or nested structures in programming languages.

PDA idea for aⁿbⁿ: push while reading a’s, then pop while reading b’s

What is a Stack? A stack is a data structure that follows the “last-in, first-out” (LIFO) principle, like a stack of plates:

• Push: Add an item to the top of the stack
• Pop: Remove the item from the top of the stack (you can only remove the most recently added item)

Think of a stack of books: you can only add a book to the top, and you can only take the top book off.

Concrete Example of a PDA:

Let’s design a PDA to recognize \(L = \{a^n b^n : n \geq 0\}\) (equal numbers of \(a\)’s followed by \(b\)’s).

Examples in \(L\): \(\epsilon\), \(ab\), \(aabb\), \(aaabbb\), … Examples NOT in \(L\): \(a\), \(ba\), \(aab\), \(abb\), …

Strategy:

1. For each \(a\) you read, push it onto the stack (counting \(a\)’s)
2. For each \(b\) you read, pop an \(a\) from the stack (matching \(b\)’s with \(a\)’s)
3. Accept if: you’ve read all input AND the stack is empty (equal counts)

Trace example - Input string “aabb”:

1. Read \(a\) → push \(A\) onto stack. Stack: [\(A\)]
2. Read \(a\) → push \(A\) onto stack. Stack: [\(A\), \(A\)]
3. Read \(b\) → pop \(A\) from stack. Stack: [\(A\)]
4. Read \(b\) → pop \(A\) from stack. Stack: []
5. Input finished, stack is empty → ACCEPT ✓

Why FSA cannot do this: An FSA has no stack, so it cannot remember the exact count of \(a\)’s. With only finitely many states, it cannot distinguish between 1000 \(a\)’s and 1001 \(a\)’s if there are more distinct counts than states. The stack gives PDAs unbounded counting ability.

3. Turing Machines (TM)

• Memory: An infinite tape (conceptually equivalent to random access memory)
• Power: “Highest” known computing power
• Examples: Any algorithm that can be computed
• Languages recognized: Recursively enumerable languages

A Turing Machine can compute anything that is computable. While the tape is technically sequential (not true random access), this does not limit computational power.

Turing machine model with a read/write head moving over an unbounded tape

What is a Turing Machine Tape? A tape is an infinite sequence of cells, each containing a symbol. The machine has a read/write head that can:

• Read the symbol in the current cell
• Write a new symbol to the current cell (overwriting the old one)
• Move left or right to an adjacent cell

Think of it like an infinitely long piece of paper with boxes, where you can write in any box and move your pencil left or right.

Why is this more powerful? Unlike a stack (where you can only access the top), a Turing Machine can:

• Move back and forth on the tape (access any previous data)
• Overwrite data (not just destructive reading like a stack)
• Use the tape for scratch work (temporary calculations)

Example of what a TM can do (but PDA cannot):

Recognize \(L = \{a^n b^n c^n : n \geq 0\}\) (equal numbers of \(a\)’s, \(b\)’s, and \(c\)’s).

Examples in \(L\): \(\epsilon\), \(abc\), \(aabbcc\), …

A TM can solve this by:

1. Crossing off one \(a\), then one \(b\), then one \(c\)
2. Moving back to the beginning
3. Repeat until all symbols are crossed off
4. Accept if all three types are exhausted simultaneously

A PDA cannot solve this because a single stack cannot count three independent quantities. This demonstrates that TM > PDA in computational power.

1.8.4 The Power Hierarchy

What do we mean by “computational power”? When we say one model is “more powerful” than another, we mean it can recognize (accept/solve) a larger class of languages (problems). Think of it like tools in a toolbox:

• A screwdriver (FSA) can tighten screws
• A power drill (PDA) can do everything a screwdriver can do, PLUS drill holes
• A full workshop (TM) can do everything the others can, PLUS cut wood, weld metal, etc.

The computational power of these models forms a strict hierarchy:

\[\text{Finite Automata} < \text{Pushdown Automata} < \text{Turing Machine}\]

This means:

• Every problem solvable by an FSA can also be solved by a PDA
• Every problem solvable by a PDA can also be solved by a TM
• There exist problems solvable by PDAs but NOT by FSAs (like \(a^n b^n\))
• There exist problems solvable by TMs but NOT by PDAs (like \(a^n b^n c^n\))

As we move to the right in the hierarchy, we can solve more complex computational problems. The extra memory capability (stack for PDA, tape for TM) is what enables this additional power.

1.9 A Course-Long Question: Unsolvable Problems

The Turing Machine is the most powerful computational model known to computer science. Any algorithm you can write in any programming language can be simulated by a Turing Machine.

This raises a fundamental question: Are there computational problems that even a Turing Machine cannot solve?

The answer is yes. There exist unsolvable problems—problems for which no algorithm can exist, even in principle. We will explore in detail what this means, why it’s true, and what the implications are for computer science.

The most famous example is the halting problem: Given an arbitrary program and input, determine whether the program will eventually stop or run forever. Alan Turing proved in 1936 that no algorithm can solve this problem for all possible programs and inputs.

Why is this important? Consider these practical implications:

• You cannot write a program that checks whether any other program has an infinite loop
• You cannot guarantee to detect all bugs that cause programs to hang
• There are fundamental limits to automated software verification

This was one of the most profound discoveries in the history of mathematics and computer science because it showed that not all clearly stated computational problems can be solved by computers. Some problems are inherently unsolvable, not because we haven’t found the right algorithm yet, but because no algorithm can possibly exist.

---

2. Definitions

• Golden Ratio (\(\phi\)): An irrational number approximately equal to 1.618, defined as the limit of the ratio of consecutive Fibonacci numbers. It appears in nature, art, and mathematics.
• Irrational Number: A real number that cannot be expressed as a ratio of two integers; its decimal representation continues forever without repeating.
• Convergence: A mathematical property where the terms of a sequence get arbitrarily close to a limiting value as the sequence progresses. The Fibonacci ratios converge to \(\phi\).
• Fibonacci Sequence: A sequence where each term is the sum of the two preceding terms, starting with 1, 1: \(F_n = F_{n-1} + F_{n-2}\) for \(n > 2\).
• Golden Rectangle: A rectangle whose side lengths are in the golden ratio (length/width = \(\phi\)).
• Golden Spiral: A logarithmic spiral that grows outward by a factor of \(\phi\) for every quarter turn, often approximated using Fibonacci sequence squares.
• Sacred Geometry: The use of geometric proportions and shapes in religious architecture and art to represent spiritual and divine concepts.
• Alberti Cipher: An early polyalphabetic substitution cipher device invented by Leon Battista Alberti in 1467, using two concentric rotating disks.
• Number Theory: A branch of pure mathematics concerned with properties of integers and related objects.
• Cryptography: The practice of secure communication through encoding and decoding information.
• RSA: A widely-used public-key cryptographic system based on the difficulty of factoring large numbers.
• Quantum Computer: A computer that uses quantum mechanical phenomena to perform computations, potentially solving certain problems much faster than classical computers.
• Theoretical Computer Science (TCS): The mathematical study of computation, including what can be computed, computational complexity, and fundamental limits of computation.
• Alphabet (\(\Sigma\)): A finite, non-empty set of symbols used to construct strings. For example, \(\{0, 1\}\) is the binary alphabet.
• String (Word): A finite sequence of symbols from an alphabet. For example, \(0101\) is a string over the binary alphabet.
• Empty String (\(\epsilon\) or \(\lambda\)): A string containing no symbols, with length zero.
• Length of a String (\(|w|\)): The number of symbols in a string. For example, \(|hello| = 5\) and \(|\epsilon| = 0\).
• Language: A set of strings over an alphabet. A language can be finite (containing a specific set of strings) or infinite (containing infinitely many strings).
• Accept (Recognize): An automaton accepts or recognizes a string if, after processing all symbols, it ends in an accepting state. An automaton recognizes a language \(L\) if it accepts exactly those strings in \(L\) and rejects all others.
• Computability: The study of which problems can be solved by algorithms, regardless of time or resource constraints.
• Complexity: The study of how efficiently problems can be solved in terms of time and space resources.
• Big O Notation (\(\mathcal{O}\)): Mathematical notation describing how an algorithm’s running time or space requirements grow with input size. For example, \(\mathcal{O}(n)\) means linear growth, \(\mathcal{O}(n^2)\) means quadratic growth.
• Computational Power: The class of problems (languages) that a computational model can solve. A model with greater computational power can recognize more languages.
• P vs NP Problem: A major unsolved question asking whether every problem whose solution can be quickly verified can also be quickly solved.
• Automaton: A mathematical model of computation consisting of states and transitions, used to recognize or generate languages.
• State: A configuration or condition of an automaton at a given moment during computation.
• Transition: A rule specifying how an automaton moves from one state to another based on input.
• Finite State Automaton (FSA): A computational model with a finite number of states and no external memory; recognizes regular languages.
• Pushdown Automaton (PDA): A computational model with a finite number of states plus a stack memory; recognizes context-free languages.
• Turing Machine (TM): The most powerful standard computational model, with a finite number of states plus an infinite tape memory; can compute anything computable.
• Stack: A last-in, first-out (LIFO) data structure supporting push (add) and pop (remove) operations.
• Regular Language: A class of formal languages that can be recognized by finite state automata.
• Context-Free Language: A class of formal languages that can be recognized by pushdown automata; includes most programming language syntax.
• Recursively Enumerable Language: A class of formal languages that can be recognized by Turing machines.
• Halting Problem: The problem of determining whether an arbitrary program will terminate or run forever; proven to be unsolvable by Turing in 1936.
• Unsolvable Problem: A computational problem for which no algorithm exists that can solve all instances of the problem.
• Formal Grammar: A set of rules for generating strings in a formal language.
• Chomsky Hierarchy: A classification of formal grammars into four types (Type 0, 1, 2, 3) based on their generative power, introduced by Noam Chomsky in 1956.
• Compiler: A program that translates source code written in a high-level programming language into machine code or another lower-level form.
• Lambda Calculus (\(\lambda\)-calculus): A formal system for expressing computation based on function abstraction and application, developed by Alonzo Church.

---

3. Formulas

• Fibonacci Sequence: \(F_1 = 1\), \(F_2 = 1\), \(F_n = F_{n-1} + F_{n-2}\) for \(n > 2\)
• Fibonacci Ratio: \(r(n) = \frac{F_{n+1}}{F_n}\), which converges to \(\phi\) as \(n \to \infty\)
• Golden Ratio: \(\phi = \lim_{n \to \infty} \frac{F_{n+1}}{F_n} \approx 1.61803398...\)
• Exact Golden Ratio: \(\phi = \frac{1 + \sqrt{5}}{2}\)

---

4. Examples

4.1. Compute Initial Fibonacci Ratios (Lecture 1, Example 1)

Calculate the first seven ratios \(r(n) = \frac{F_{n+1}}{F_n}\) for the Fibonacci sequence and observe their behavior.

Click to see the solution

Key Concept: The Fibonacci sequence is defined as \(F_1 = 1\), \(F_2 = 1\), \(F_n = F_{n-1} + F_{n-2}\). We calculate successive ratios to observe convergence to the golden ratio.

1. Generate Fibonacci numbers:
   • \(F_1 = 1\)
   • \(F_2 = 1\)
   • \(F_3 = F_2 + F_1 = 1 + 1 = 2\)
   • \(F_4 = F_3 + F_2 = 2 + 1 = 3\)
   • \(F_5 = F_4 + F_3 = 3 + 2 = 5\)
   • \(F_6 = F_5 + F_4 = 5 + 3 = 8\)
   • \(F_7 = F_6 + F_5 = 8 + 5 = 13\)
   • \(F_8 = F_7 + F_6 = 13 + 8 = 21\)
2. Calculate ratios \(r(n) = \frac{F_{n+1}}{F_n}\):
   • \(r(1) = \frac{F_2}{F_1} = \frac{1}{1} = 1.000\)
   • \(r(2) = \frac{F_3}{F_2} = \frac{2}{1} = 2.000\)
   • \(r(3) = \frac{F_4}{F_3} = \frac{3}{2} = 1.500\)
   • \(r(4) = \frac{F_5}{F_4} = \frac{5}{3} \approx 1.667\)
   • \(r(5) = \frac{F_6}{F_5} = \frac{8}{5} = 1.600\)
   • \(r(6) = \frac{F_7}{F_6} = \frac{13}{8} = 1.625\)
   • \(r(7) = \frac{F_8}{F_7} = \frac{21}{13} \approx 1.615\)
3. Observe the pattern:
   • Odd-indexed ratios (\(r(1), r(3), r(5), r(7)\): 1.000, 1.500, 1.600, 1.615) are less than \(\phi \approx 1.618\)
   • Even-indexed ratios (\(r(2), r(4), r(6)\): 2.000, 1.667, 1.625) are greater than \(\phi \approx 1.618\)
   • The ratios oscillate around \(\phi\), converging from above and below

Answer: The ratios are 1, 2, 1.5, 1.67, 1.6, 1.625, 1.6125, converging to the golden ratio \(\phi \approx 1.618\).

4.2. Identify Computational Models (Lecture 1, Example 2)

Given the following real-world systems, identify which computational model (FSA, PDA, or TM) best describes each:

1. An elevator system
2. A programming language compiler
3. A general-purpose computer

Click to see the solution

Key Concept: Different computational models have different memory capabilities and power. Match the system requirements to the appropriate model.

(a) Elevator System:

An elevator has a finite number of possible configurations (floor positions, door states, button states). It doesn’t need to remember an unbounded history or process nested structures.

Answer: Finite State Automaton (FSA) - The elevator transitions between a finite set of states based on button presses and floor sensors.

(b) Programming Language Compiler:

Compilers must parse nested structures like:

• Nested parentheses: ((()))
• Nested blocks: { { } }
• Nested function calls: f(g(h(x)))

These require a stack to match opening and closing delimiters.

Answer: Pushdown Automaton (PDA) - The compiler uses a stack-based parser to handle nested language structures.

(c) General-Purpose Computer:

A general-purpose computer can execute arbitrary algorithms, access memory at any location, and solve any computable problem.

Answer: Turing Machine (TM) - This represents the highest computational power, equivalent to any algorithm you can write.

Summary:

• (a) FSA (finite states, no external memory needed)
• (b) PDA (stack memory for nested structures)
• (c) TM (full computational power)

4.3. Understanding the Power Hierarchy (Lecture 1, Example 3)

Explain why the statement “Every problem solvable by an FSA can also be solved by a PDA” is true, but the converse is not.

Click to see the solution

Key Concept: The power hierarchy shows that more powerful models can simulate less powerful ones, but not vice versa.

1. FSA to PDA simulation:
   • A PDA has all the capabilities of an FSA (finite states and transitions) plus a stack
   • To simulate an FSA using a PDA, simply ignore the stack—never push or pop anything
   • The PDA behaves exactly like the original FSA
   • Therefore, any problem solvable by an FSA can be solved by a PDA
2. Why the converse fails:
   • Some problems require the stack memory that PDAs provide
   • Example: Recognizing the language \(L = \{a^n b^n : n \geq 0\}\) (equal numbers of \(a\)’s followed by equal numbers of \(b\)’s)
   • A PDA can solve this:
     • Push each \(a\) onto the stack
     • For each \(b\), pop an \(a\) from the stack
     • Accept if the stack is empty at the end
   • An FSA cannot solve this:
     • With only finite memory (states), it cannot count arbitrarily large numbers of \(a\)’s
     • After seeing, say, 1000 \(a\)’s, it has no way to remember this exact count
     • It will confuse 1000 \(a\)’s with 1001 \(a\)’s (pigeonhole principle)
3. Conclusion:
   • The extra memory capability of PDAs allows them to solve problems FSAs cannot
   • This demonstrates that PDA > FSA in computational power

Answer: Every FSA problem can be solved by a PDA because PDAs can simulate FSAs by ignoring their stack. However, PDAs can solve problems requiring stack memory (like matching nested structures) that FSAs cannot handle, proving PDAs are strictly more powerful.

4.4. Trace an FSA Execution (Lecture 1, Example 4)

Consider an FSA that recognizes strings with an even number of \(1\)’s over alphabet \(\{0, 1\}\), with states:

• \(q_0\) (EVEN state, accepting): “Seen an even number of \(1\)’s”
• \(q_1\) (ODD state, non-accepting): “Seen an odd number of \(1\)’s”

Trace the execution of this FSA on the input string “\(101\)”. Does the FSA accept or reject?

Click to see the solution

Key Concept: To trace an FSA, start in the initial state and follow transitions for each input symbol. Accept if you end in an accepting state.

Transitions:

• From \(q_0\): read \(0\) → stay in \(q_0\); read \(1\) → go to \(q_1\)
• From \(q_1\): read \(0\) → stay in \(q_1\); read \(1\) → go to \(q_0\)

Start state: \(q_0\) (even count) Accepting states: \(\{q_0\}\)

Trace for input “\(101\)”:

1. Initial state: \(q_0\) (EVEN) - we’ve seen 0 ones
2. Read \(1\): Transition from \(q_0\) to \(q_1\) (now seen 1 one - ODD)
3. Read \(0\): Stay in \(q_1\) (still 1 one - ODD)
4. Read \(1\): Transition from \(q_1\) to \(q_0\) (now seen 2 ones - EVEN)
5. End of input: Current state is \(q_0\), which is an accepting state

Answer: The FSA ACCEPTS the string “\(101\)” because it ends in accepting state \(q_0\). This is correct because “\(101\)” contains two \(1\)’s (an even number).

4.5. Understanding Language Notation (Lecture 1, Example 5)

For each of the following, determine whether the string is in the language:

1. Is “\(aabb\)” in \(L = \{a^n b^n : n \geq 0\}\)?
2. Is “\(aab\)” in \(L = \{a^n b^n : n \geq 0\}\)?
3. Is “\(\epsilon\)” (empty string) in \(L = \{a^n b^n : n \geq 0\}\)?

Click to see the solution

Key Concept: The notation \(a^n b^n\) means “exactly \(n\) \(a\)’s followed by exactly \(n\) \(b\)’s” for some non-negative integer \(n\). The language includes all such strings for all possible values of \(n \geq 0\).

(a) Is “\(aabb\)” in \(L\)?

Count the symbols:

• Number of \(a\)’s: 2
• Number of \(b\)’s: 2
• Are they equal? Yes (both are 2)
• Form: \(aa\) followed by \(bb\) = \(a^2 b^2\)

This matches the pattern \(a^n b^n\) with \(n = 2\).

Answer: YES, “\(aabb\)” \(\in L\)

(b) Is “\(aab\)” in \(L\)?

Count the symbols:

• Number of \(a\)’s: 2
• Number of \(b\)’s: 1
• Are they equal? No (2 ≠ 1)

This does NOT match the pattern \(a^n b^n\) for any value of \(n\).

Answer: NO, “\(aab\)” \(\notin L\)

(c) Is “\(\epsilon\)” (empty string) in \(L\)?

The empty string has:

• Number of \(a\)’s: 0
• Number of \(b\)’s: 0
• Are they equal? Yes (both are 0)
• Form: \(a^0 b^0 = \epsilon\)

This matches the pattern \(a^n b^n\) with \(n = 0\) (the notation “\(n \geq 0\)” explicitly allows this).

Answer: YES, \(\epsilon \in L\)

General rule: When a language is defined with “\(n \geq 0\)”, always check if the empty string is included (it corresponds to \(n = 0\)).